package mht.practice.ListNode;

/**
 * Created by MHT on 2017/9/15.
 */
public class mergeSortedList {

    /**
     * 已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序
     * 这个类似归并排序。尤其注意两个链表都为空，和其中一个为空时的情况。
     * 只需要O（1）的空间。时间复杂度为O（max(len1, len2)）
     */
    public static ListNode mergeSortedList(ListNode head1, ListNode head2) {
        // 其中一个链表为空的情况，直接返回另一个链表头，O(1)
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }

        ListNode mergeHead = null;
        // 先确定下来mergeHead是在哪里
        if (head1.val < head2.val) {
            mergeHead = head1;
            head1 = head1.next;         // 跳过已经合并了的元素
            mergeHead.next = null;  // 断开mergeHead和后面的联系
        } else {
            mergeHead = head2;
            head2 = head2.next;
            mergeHead.next = null;
        }

        ListNode mergeCur = mergeHead;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                mergeCur.next = head1;       // 把找到较小的元素合并到merge中
                head1 = head1.next;              // 跳过已经合并了的元素
                mergeCur = mergeCur.next;    // 找到下一个准备合并的元素
                mergeCur.next = null;            // 断开mergeCur和后面的联系
            } else {
                mergeCur.next = head2;
                head2 = head2.next;
                mergeCur = mergeCur.next;
                mergeCur.next = null;
            }
        }

        // 合并剩余的元素
        if (head1 != null) {
            mergeCur.next = head1;
        } else if (head2 != null) {
            mergeCur.next = head2;
        }

        return mergeHead;
    }


    /**
     * 递归合并两链表
     */
    public static ListNode mergeSortedListRec(ListNode head1, ListNode head2) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }

        ListNode mergeHead = null;
        if (head1.val < head2.val) {
            mergeHead = head1;
            // 连接已解决的子问题
            mergeHead.next = mergeSortedListRec(head1.next, head2);
        } else {
            mergeHead = head2;
            mergeHead.next = mergeSortedListRec(head1, head2.next);
        }
        return mergeHead;
    }
}
